package com.dh.leetcode.k1;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * ClassName: _1765_map_of_highest_peak
 * @Description: 1765. 地图中的最高点
 * 给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。
 *
 * 如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。
 * 如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。
 * 你需要按照如下规则给每个单元格安排高度：
 *
 * 每个格子的高度都必须是非负的。
 * 如果一个格子是是 水域 ，那么它的高度必须为 0 。
 * 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）
 * 找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。
 *
 * 请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：isWater = [[0,1],[0,0]]
 * 输出：[[1,0],[2,1]]
 * 解释：上图展示了给各个格子安排的高度。
 * 蓝色格子是水域格，绿色格子是陆地格。
 * 示例 2：
 *
 *
 *
 * 输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
 * 输出：[[1,1,0],[0,1,1],[1,2,2]]
 * 解释：所有安排方案中，最高可行高度为 2 。
 * 任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。
 *
 *
 * 提示：
 *
 * m == isWater.length
 * n == isWater[i].length
 * 1 <= m, n <= 1000
 * isWater[i][j] 要么是 0 ，要么是 1 。
 * 至少有 1 个水域格子。
 *
 * https://leetcode-cn.com/problems/map-of-highest-peak/
 *
 * @author shouzimu
 * @date 2022/1/29 22:25
 */
public class _1765_map_of_highest_peak {
    int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    /**
     * 多源 BFS 参考：三叶姐
     *
     * https://leetcode-cn.com/problems/map-of-highest-peak/solution/gong-shui-san-xie-duo-yuan-bfs-yun-yong-8sw0f/
     *
     * @param isWater
     * @return
     */
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length, n = isWater[0].length;
        int[][] res = new int[m][n];
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    queue.add(new int[]{i, j});
                } else {
                    res[i][j] = -1;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] xy = queue.poll();
            int dx = xy[0];
            int dy = xy[1];
            for (int[] dir : dirs) {
                int nx = dx + dir[0], ny = dy + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                if (res[nx][ny] != -1) {
                    continue;
                }
                queue.add(new int[]{nx, ny});
                res[nx][ny] = res[dx][dy] + 1;
            }
        }

        return res;
    }

    @Test
    public void highestPeakTest() {
        Assert.assertEquals(Arrays.deepToString(new int[][]{{1, 0}, {2, 1}}),
                Arrays.deepToString(highestPeak(new int[][]{{0, 1}, {0, 0}})));
        Assert.assertEquals(Arrays.deepToString(new int[][]{{1, 1, 0}, {0, 1, 1}, {1, 2, 2}}),
                Arrays.deepToString(highestPeak(new int[][]{{0, 0, 1}, {1, 0, 0}, {0, 0, 0}}
                )));
        Assert.assertEquals(Arrays.deepToString(new int[][]{{4}, {3}, {2}, {1}, {0}, {1}, {1}, {0}, {0}}),
                Arrays.deepToString(highestPeak(new int[][]{{0}, {0}, {0}, {0}, {1}, {0}, {0}, {1}, {1}}
                )));
    }

}
